package com.hc.programming.math;

/**
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * <p>
 * 给定 n 和 k，返回第 k 个排列。
 * 示例 1：
 * 输入：n = 3, k = 3
 * 输出："213"
 * 示例 2：
 * 输入：n = 4, k = 9
 * 输出："2314"
 * 示例 3：
 * 输入：n = 3, k = 1
 * 输出："123"
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/8/30 16:47
 */
public class 排列序列 {

    public static void main(String[] args) {
        System.out.println("4,2==1243: " + getPermutation(4, 2));
        System.out.println("4,3==1324: " + getPermutation(4, 3));
        System.out.println("4,23==4312: " + getPermutation(4, 23));
        System.out.println("4,13==3124: " + getPermutation(4, 13));
    }

    public static String getPermutation(int n, int k) {
        if (n <= 1) return "1";
        // 初始化阶乘数组
        int[] arrange = new int[n + 1];
        arrange[1] = 1;
        for (byte i = 2; i <= n; i++) {
            arrange[i] = i * arrange[i - 1];
        }
//        System.out.println(Arrays.toString(arrange));
        byte[] nums = new byte[n + 1]; // 位数组
        for (int i = n; i > 0; i--) {
            if (k >= arrange[i]) {
                nums[i] = (byte) (k / arrange[i]);
                k = k % arrange[i];
            }
        }
//        System.out.println(Arrays.toString(nums));
        // 转换成数字
        short temp = 0;
        for (byte i = 0; i < n; i++) {
            temp += nums[i];
        }
        byte[] arr = new byte[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        StringBuilder sb = new StringBuilder();

        for (int i = n; i > 0; i--) {
            if (temp == 0) { // 直接倒排列，如 [0,0,0,1]
                break;
            }
            int idx = (temp == nums[i - 1]) ? nums[i - 1] : nums[i - 1] + 1;
            temp -= nums[i - 1];

            for (byte j = 1; j <= n; j++) {
                if (arr[j] != 0 && (--idx) == 0) {
                    sb.append(arr[j]);
                    arr[j] = 0;
                    break;
                }
            }
        }
        if (sb.length() < n) {
            for (int i = n; i > 0; i--) {
                if (arr[i] != 0) {
                    sb.append(arr[i]);
                }
            }
        }

        return sb.toString();
    }

}
